
#include<stdio.h>

int main()
{
	int n,i,a[50];
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		int x,m,t=0,j,s=0;
		scanf("%d",&x);
		while (x!=0)
		{
			m=x%10;
			for (j=0;j<t;j++)
				m=m*9;
			s=s+m;
			t++;
			x=x/10;
		}
		t=0;
		while (s!=0)
		{
			a[t]=s%2;
			s=s/2;
			t++;
		}
		t--;
		for (j=t;j>=0;j--)
			printf("%d",a[j]);
		printf("\n");
	}
	return 0;
}
